import collections
import copy
from functools import reduce
from typing import List


"""
错误解：

这里有个重大的bug
在依靠关系图进行搜索的时候 却对关系图进行修改
在搜索过程中关系图变化了 这使得整个过程变得不可预测
自己在写代码的时候 脑子中默认的是 关系图不改变，实际实现的时候却违法了这样的原则
这个问题就像是在循环数组过程中改变数组，让整个循环不可控
这样的编程实现方式是不可靠的

这个问题出现原因是 自己没有完全理清楚算法是否可行之前就直接实现，后面又想对这个算法修修补补 来希望勉强实现
实际上是越打补丁 算法越混乱 越难维护 然后就失控了
最后是整题需要重新构思 然后重新实现

"""
class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        """
        从后往前，去掉一条边以后，对每个节点进行并查集的处理。
        进行路径优化
        """

        relations = collections.defaultdict(set)

        for edge in edges:
            father, child = edge
            relations[child].add(father)

        def withoutOneEdge(edge):
            rs = copy.deepcopy(relations)
            f, c = edge
            rs[c].remove(f)
            print(rs)

            def getF(nodeID):
                if (nodeID not in rs) or (len(rs[nodeID]) == 0):
                    return nodeID
                else:
                    for fID in rs[nodeID]:
                        rs[nodeID].remove(fID)
                        f = getF(fID)
                        rs[nodeID].add(f)
            """
            这里有个重大的bug
            在依靠关系图进行搜索的时候 却对关系图进行修改
            在搜索过程中关系图变化了 这使得整个过程变得不可预测
            自己在写代码的时候 脑子中默认的是 关系图不改变，实际实现的时候却违法了这样的原则
            这个问题就像是在循环数组过程中改变数组，让整个循环不可控
            这样的编程实现方式是不可靠的
            
            这个问题出现原因是 自己没有完全理清楚算法是否可行之前就直接实现，后面又想对这个算法修修补补 来希望勉强实现
            实际上是越打补丁 算法越混乱 越难维护 然后就失控了
            最后是整题需要重新构思 然后重新实现
            """

            """
            这题还是得按 题解的方式来解决
            """
            f_tmp = set()
            for nodeID in rs:
                if getF(nodeID) == nodeID:
                    f_tmp.add(nodeID)

            print(rs)
            print(f_tmp)

            fathers = [f_set for f_set in rs.values()]
            union = reduce(lambda x, y: x & y, fathers)
            if f_tmp:
                union = f_tmp & union
            if len(union) == 1:
                return True
            return False

        for edge in edges[::-1]:
            if withoutOneEdge(edge) == True:
                return edge


edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]
print(Solution().findRedundantDirectedConnection(edges))
